#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
using namespace std;

class Solution {
public:

    void mergesort(vector<int>& nums, vector<int>& index, vector<int>& tmp1, vector<int>& tmp2, vector<int>& ret, int begin, int end)
    {
        if (begin >= end) return;
        int mid = (begin + end) / 2;
        mergesort(nums, index, tmp1, tmp2, ret, begin, mid);
        mergesort(nums, index, tmp1, tmp2, ret, mid + 1, end);
        int cur1 = begin, cur2 = mid + 1, i = begin;
        while (cur1 <= mid && cur2 <= end)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tmp1[i] = nums[cur2];
                tmp2[i++] = index[cur2++];
            }
            else
            {
                tmp1[i] = nums[cur1];
                //cout<<"nums[cur1]:"<<nums[cur1]<<endl;
                //cout<<"cur1:"<<cur1<<endl;
                //cout<<"index[cur1]:"<<index[cur1]<<endl;
                ret[index[cur1]] += end - cur2 + 1;
                tmp2[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid) { tmp1[i] = nums[cur1]; tmp2[i++] = index[cur1++]; }
        while (cur2 <= end) { tmp1[i] = nums[cur2]; tmp2[i++] = index[cur2++]; }
        for (int j = begin; j <= end; ++j)
        {
            nums[j] = tmp1[j];
            index[j] = tmp2[j];
        }
        // for(auto e:nums) cout<<e<<" ";
        // cout<<endl;
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp1(n);
        vector<int> tmp2(n);
        vector<int> ret(n);
        vector<int> index(n);
        for (int i = 0; i < n; ++i) index[i] = i;
        mergesort(nums, index, tmp1, tmp2, ret, 0, n - 1);
        return ret;
    }
};